The present invention relates to a linear feedback shift register circuit suitable for providing respective digital samples at successive time instants, each of which samples represents a linear combination of prior digital samples and comprises M significant bits together with an optional addition of X sign extension bits, where X may optionally be zero, said circuit comprising N similar cells each of which forms a bit flow path comprising in series between a main input and a main output of said cell: a P-bit upstream register; a weighting operator; a two-input combining operator; and a Q-bit downstream register; with the output from the upstream register and one of the two inputs to the combining operator respectively constituting a secondary output and a secondary input of the cell suitable for being respectively connected to a main input and to a main output of a following cell in the circuit, and with the main output of the first cell being fed back to the main input of said cell in order to allow the digital samples produced to be recirculated.
Linear feedback shift register circuits have been used for several years and are generally known under the English term or its abbreviation "LFSR".
The function of these circuits is to take N initial digital samples, e.g. S1 to SN, and to produce new digital samples generically written Sj, for example, and each represented for j greater than N by the linear combination: ##EQU1## where (ki) constitute a set of N weighting coefficients.
FIG. 1 is a diagram of a first type of prior art LFSR. This LFSR, which does not include all of the features mentioned in the introduction, comprises registers (e.g. RG1 to RG5), weighting operators OP1 to OP5 which are constituted, for example, by multipliers which multiply by respective constant coefficients k1 to k5, and a combining operator OC.
In this LFSR, the bit flow paths which are represented by single lines are constituted, in fact, by paths for parallel bit flow, and are therefore each constituted by a plurality of parallel lines. Similarly, the registers and the operators are parallel-operating registers and operators, i.e. each of them acts on a plurality of bits at a time.
The combining operator OC which is represented diagrammatically as a single adder is not physically constituted in this particular form.
In general, a parallel operator such as OC takes the form of a pyramid of elementary triad operators (i.e. operators having two inputs and one output), as shown in FIG. 2.
Suppose that at instant 0, registers RG1 to RGN contain samples SN to S1.
During the first operating cycle, each digital sample passes from one register to the next register and is simultaneously weighted by the operator OP connected to the output of the register it is leaving; the weighted samples are then simultaneously transmitted to the combining operator OC.
At the end of the operating cycle, the combining operator OC (assumed to be constituted by the FIG. 2 conventional parallel adder) thus provides a digital sample: ##EQU2## which is stored in the register RG1.
Such an LFSR therefore provides the desired function which consists in providing digital samples represented by linear combinations of earlier samples.
However, given the structure of its combining operator OC as shown in FIG. 2, an LFSR of this type is not suitable for being described as an assembly of N similar cells.
This lack of modular structure is a handicap in making an LFSR of this type in the form of very large scale integration (VLSI) circuits. The geometry of the physical location of the elementary triad operators constituting the combining operator OC, and also the transfer time of said operator both depend on the number N of register RG1, RG2, . . . , RGN in the circuit.
This drawback is avoided, in conventional manner, by using a structure such as the LFSR structure shown in FIG. 3.
Although such a circuit still does not include all of the features specified in the introduction, it nevertheless provides a modular structure since it comprises an assembly of N similar cells referenced C1 to CN.
Each cell constitutes a parallel bit flow path comprising a series connection of a register such as RG1 to RGN, a weighting operator such as OP1 to OPN, and a combining operator such as OC1 to OCN.
Like the FIG. 1 LFSR, the registers and the weighting and the combining operators operate in parallel, i.e. the single lines shown connecting them to one another in the diagram of FIG. 3 are in fact constituted by M parallel lines where M is the number of bits in each of the digital samples contained in the registers RG1 to RGN.
The FIG. 3 LFSR includes a multiplexer MX enabling the input to the register RG1 to be connected either to an input E to the LFSR circuit or else to the output from the combining operator OC1.
In point of fact, such a multiplexer is also required in the FIG. 1 LFSR, and it has been omitted from FIG. 1 simply for the purpose of simplifying understanding.
During an initialization stage, the multiplexer MX in the FIG. 3 LFSR connects the input E thereof to the register RG1 so as to provide access to this circuit for digital samples S1 to SN which are initially applied to the input E and which, at the end of the initialization stage, occupy respective ones of the registers RGN to RG1. The multiplexer MX is then switched to connect the output from the combining operator OC1 to the input to the register RG1, thereby enabling new digital samples to be generated by circulating the initial samples S1 to SN and by the processing provided by the various operators.
During each calculation cycle, the digital samples stored in the registers RG1 to RGN are simultaneously transmitted to the respective following registers and also to the respective weighting operators OP1 to OPN in which they are multiplied by respective constant coefficients k1 to kN.
Thus, the weighted digital samples are all simultaneously available at the top inputs to the respective operators OC1 to OCN.
The sum of these weighted samples is then returned to the first register RG1 via the parallel multiplexer MX. However, this sample sum becomes available at the bottom input to the multiplexer MX only after the sample weighted by the coefficient kN in the furthest cell from the multiplexer MX has passed through all of the combining operators, i.e. OCN to OC1, and this requires time approximately equal to N times the transfer time through a single combining operator such has OC1.
Consequently, even though the FIG. 3 LFSR has the advantage of modular structure describable as an assembly of N similar cells, it nevertheless retains the drawback of leading to cycle times which depend on the number N of cells.
This dependence of the time required for calculating each cycle as a function of the number of cells can be eliminated, in known manner, by the LFSR shown in FIG. 4.
This LFSR satisfies all of the features specified at the beginning of the present description and represents the closest prior art to the invention.
The FIG. 4 LFSR is described, for example, at page 43 (FIG. 10) of the January 1982 number of the journal "Computer", in an article by H.T. Kung (Carnegie-Mellon University).
As in the FIG. 3 LFSR, the bit flow paths and the operators in the FIG. 4 LFSR are parallel in structure.
Constructionally speaking, the FIG. 4 LFSR differs from the FIG. 3 LFSR solely in that each cell (such as C1 to CN) of the FIG. 4 circuit, instead of comprising a single register (such as RG1 to RGN), comprises a P-bit upstream register (such as RGE1 to RGEN) together with a Q-bit downstream register such as RGS1 to RGSN).
In this prior art, the lengths P and Q of the upstream and downstream registers are equal.
The structural difference between the LFSRs of FIGS. 3 and 4 is accompanied by an operating difference which gives rise to different performance.
In the FIG. 4 LFSR, initialization is performed by alternately injecting via the multiplexer MX a useful digital sample such as S1 to SN and a null sample, i.e. a sample in which all the bits are equal to zero.
Since there are N useful digital samples there are also N null samples such that the initialization stage takes N+N=2N cycles.
Since there are N upstream registers RGE1 to RGEN and N downstream registers RGS1 to RGSN, all of the registers are loaded at the instant at which the initialization phase terminates.
More precisely, at this instant, half of the upstream registers are filled with null samples and the other half of them are filled with samples from the second half of the digital samples S1 to SN, while the downstream registers already contain partial combinations of weighted digital samples.
However, in each cycle each digital sample follows an elementary path which corresponds to the distance between two registers.
In summary, the FIG. 4 LFSR thus has the advantage of a modular structure and also of generating (after its initialization stage) each of the digital samples in a time which is independent of the number N of digital samples being used.
The term of art for such an LFSR is "systolic".
However, this prior LFSR suffers from two drawbacks: the first is that it requires an initialization stage of 2N cycles for N useful samples, and the second is that under stationary conditions it provides a new useful digital sample only on every other cycle since every in-between sample produced is constituted by a null sample.